package test32;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-04-25
 * Time: 15:58
 */
import java.util.*;
import java.io.*;
import java.math.*;

public class Main1 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String str = null;
        while ((str = br.readLine()) != null && !str.equals("")) {
            int n = Integer.parseInt(str);
            int[] arr = new int[100001];
            arr[0] = 1;
            arr[1] = 1;
            for (int i = 2; i < 100001; i++) {
                arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000;
            }
            System.out.printf((n < 29 ? "%d\n" : "%06d\n"),arr[n]);
        }
        br.close();
    }
}



//import java.util.Scanner;
//
///**
// * @Author Huang
// * @Title
// * @Date 2022/5/31 10:50
// */
//public class Main{
//    static int[] fibArr = new int[100001];
//    public static void main(String[] args) {
//        setFibArr();
//        Scanner sc = new Scanner(System.in);
//        while (sc.hasNextInt()) {
//            int n = sc.nextInt();
//            System.out.printf((n < 29 ? "%d\n" : "%06d\n"),fibArr[n]);
//        }
//    }
//
//    public static void setFibArr() {
//        fibArr[0] = 1;
//        fibArr[1] = 1;
//        for (int i = 2; i < 100001; i++) {
//            fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]) % 1000000;
//        }
//    }
//}